package com.lw.leetcode.back.c;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * back
 * 1994. 好子集的数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/2/22 10:44
 */
public class NumberOfGoodSubsets {


    public static void main(String[] args) {
        NumberOfGoodSubsets test = new NumberOfGoodSubsets();

        // 6
//        int[] arr = {1,2,3,4};

        // 5368
        int[] arr = {5, 10, 26, 24, 21, 24, 23, 11, 12, 27, 4, 17, 16, 2, 6, 6, 8, 13, 30, 24, 20, 2, 19, 1, 1, 1};

        // 671
//        int[] arr = {5, 10, 26, 21, 23, 11, 17, 2, 6, 6, 13, 30, 2, 19};

        // 59
//        int[] arr = {5, 10, 26, 21, 11, 2, 6, 13, 30};

        // 5
//        int[] arr = {4,2,3,15};

        // 382
//        int[] arr = {1,2,3,4,14,23,5,4,3,15,17,12,6,8,27,24,23,2,6,16};

        // 55
//        int[] arr = {5, 4, 3, 15, 17, 12, 6, 8, 27, 24, 23, 2, 6, 16};

        // 47
//        int[] arr = {5, 4, 3, 15, 17, 12, 6, 8, 27, 24, 23, 2, 16};

        // 7
//        int[] arr = {6, 8, 27, 24, 23, 2, 6, 16};
        // 17
//        int[] arr = {5, 10, 26,  2, 6, 13, 30};

        int i = test.numberOfGoodSubsets(arr);
        System.out.println(i);

    }


    private long count;

    public int numberOfGoodSubsets(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        Map<Integer, Integer> countMap = new HashMap<>();
        initMap(countMap);
        int zz = 0;
        for (int num : nums) {
            if (num == 1) {
                zz++;
                continue;
            }
            Integer c = countMap.get(num);
            if (c != null) {
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
        }

        int length = map.size();
        int[] items = new int[length];
        int i = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            items[i++] = (entry.getKey() << 18) + entry.getValue();
        }

        for (int j = 0; j < length; j++) {
            int v = items[j];
            int c = v & 0X3FFFF;
            count = (count + c) % 1000000007L;
            find(items, j + 1, v >> 18, c);
        }

        long tt = 1L;
        for (int i1 = 0; i1 < zz; i1++) {
            tt <<= 1;
            tt %= 1000000007L;
        }
        return (int) ((count * tt) % 1000000007L);
    }

    private void find(int[] items, int index, int item, long cc) {
        if (index < items.length) {
            int v = items[index];
            int k = v >> 18;
            if ((item & k) == 0) {
                long ccc = (cc * (v & 0X3FFFF)) % 1000000007L;
                count = (count + ccc) % 1000000007L;
                find(items, index + 1, item | k, ccc);
            }
            find(items, index + 1, item, cc);
        }
    }

    private void initMap(Map<Integer, Integer> countMap) {
        countMap.put(2, 1);
        countMap.put(3, 2);
        countMap.put(5, 4);
        countMap.put(6, 3);
        countMap.put(7, 8);
        countMap.put(10, 5);
        countMap.put(11, 16);
        countMap.put(13, 32);
        countMap.put(14, 9);
        countMap.put(15, 6);
        countMap.put(17, 64);
        countMap.put(19, 128);
        countMap.put(21, 10);
        countMap.put(22, 17);
        countMap.put(23, 256);
        countMap.put(26, 33);
        countMap.put(29, 512);
        countMap.put(30, 7);
    }

}
